package Tree;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/**
 * @Author: zhang
 * @Description:
 * @Date: Created in 19:58 2019/9/30
 */


public class BinaryTreeTest {
    //创建树节点
    class TreeNode {
        private char val;
        private TreeNode left;
        private TreeNode right;

        public TreeNode(char val) {
            this.val = val;
        }
    }

    public static void main(String[] args) {
        BinaryTreeTest test = new BinaryTreeTest();
        String s = "ABC##DE#G##F###";
        TreeNode root = test.createTree(s);

        System.out.print("前序：");
        test.preorderTree(root);
        System.out.println();
        test.preorderNoRe(root);
        System.out.println();

        System.out.print("中序：");
        test.midorderTree(root);
        System.out.println();
        test.midorderNoRe(root);
        System.out.println();

        System.out.print("后序：");
        test.lastorderTree(root);
        System.out.println();
        test.postorderNoRe(root);
        System.out.println();

        System.out.print("层序：");
        test.orderBinaryTree(root);
        System.out.println();

        System.out.println(test.completeTree(root));
        /*System.out.println("节点个数：" + test.nodeCount(root));
        System.out.println("输的深度：" + test.HeightOfTree(root));*/
    }


    //1、根据字符串创建树
    public int i = 0;

    public TreeNode createTree(String s) {
        TreeNode root = null;
        //如果不为#,创建一个节点，这里通过前序方式创建
        char ch = s.charAt(i);
        if (ch != '#') {
            root = new TreeNode(ch);
            i++;
            //递归创建左节点、右节点
            root.left = createTree(s);
            root.right = createTree(s);
        } else {
            i++;
        }
        return root;
    }

    //2、计算树的节点个数
    public int nodeCount(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return nodeCount(root.left) + nodeCount(root.right) + 1;
    }

    //3、树的深度
    public int HeightOfTree(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int leftHeight = HeightOfTree(root.left);
        int rightHeight = HeightOfTree(root.right);
        return Math.max(leftHeight, rightHeight) + 1;
    }

    /******************三种遍历方式：递归********************/
    //前序遍历
    public void preorderTree(TreeNode root) {
        if (root == null) {
            return;
        }
        System.out.print(root.val + " ");
        preorderTree(root.left);
        preorderTree(root.right);
    }

    //中序遍历
    public void midorderTree(TreeNode root) {
        if (root == null) {
            return;
        }
        midorderTree(root.left);
        System.out.print(root.val + " ");
        midorderTree(root.right);
    }

    //后序遍历
    public void lastorderTree(TreeNode root) {
        if (root == null) {
            return;
        }
        lastorderTree(root.left);
        lastorderTree(root.right);
        System.out.print(root.val + " ");
    }

    /*********************非递归遍历***************************/
    /*前序遍历
     * 前序非递归：通过栈来实现
     * 如果左边不为空，打印后入栈
     * 如果左边为空，出栈得到栈顶元素，重新指向右结点
     * 继续看左边是否为空。。。
     * 特别注意：外层循环加一个条件：当栈不为空时还可以循环*/
    public void preorderNoRe(TreeNode root) {
        TreeNode cur = root;
        TreeNode top = null;
        Stack<TreeNode> stack = new Stack<>();
        while (cur != null || !stack.isEmpty()) {
            while (cur != null) {
                System.out.print(cur.val + " ");
                stack.push(cur);
                //遍历左边结点
                cur = cur.left;
            }
            //此时左边结点遍历完成，遍历右边结点
            top = stack.pop();
            cur = top.right;
        }
    }

    //中序遍历
    public void midorderNoRe(TreeNode root){
        TreeNode cur = root;
        TreeNode top = null;
        Stack<TreeNode> stack = new Stack<>();
        while(cur != null || !stack.isEmpty()){
            while(cur != null){
                stack.push(cur);
                cur = cur.left;
            }
            top = stack.pop();
            System.out.print(top.val+" ");
            cur = top.right;
        }
    }

    //后序遍历
    public void postorderNoRe(TreeNode root){
        TreeNode cur = root;
        TreeNode pre = null;
        Stack<TreeNode> stack = new Stack<>();
        while(cur != null || !stack.isEmpty()){
            while(cur != null){
                stack.push(cur);
                cur = cur.left;
            }
            //此时左结点遍历完成
            cur = stack.peek();
            //这个地方增加一个条件cur.right == pre，防止重复打印
            if(cur.right == null || cur.right == pre){
                System.out.print(cur.val+" ");
                stack.pop();
                pre = cur;//标记最近一次打印的结点
                cur = null;
            }else{
                cur = cur.right;
            }
        }
    }

    /***************************层序遍历****************************/
    public void orderBinaryTree(TreeNode root){
        Queue<TreeNode> queue = new LinkedList<>();
        if(root != null){
            queue.add(root);
        }
        while(!queue.isEmpty()){
            TreeNode cur = queue.peek();
            System.out.print(cur.val+" ");
            queue.poll();
            if(cur.left != null){
                queue.add(cur.left);
            }
            if(cur.right != null){
                queue.add(cur.right);
            }
        }
    }

    //是否为完全二叉树
    public boolean completeTree(TreeNode root){
        Queue<TreeNode> queue = new LinkedList<>();
        if(root != null){
            queue.add(root);
        }
        while(!queue.isEmpty()){
            TreeNode cur = queue.poll();
            if(cur != null){
                queue.add(cur.left);
                queue.add(cur.right);
            }else{
                break;
            }
        }
        while(!queue.isEmpty()){
            if(queue.poll() != null){
                return false;
            }
        }
        return true;
    }

}
